package BinaryTree;

import MyUtils.MHUtils;
import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

import 其他.DataStructure.TreeNode;

/**
 * LBLD框架 基础上 开始写
 * <p>
 * 1 广度 的 核心append pt 操作
 * 放到 下方迭代处 （ cur不处理业务 ）
 * 2 广度 必须 q.add(root)
 * <p>
 * 难点：null的处理
 * 反序列化 cur=null continue
 * 序列化 还有 核心操作(操作res的) 的 位置
 */
public class 二叉树的序列化与反序列化297 {

    /*
      new：
          while草图别画栈
          而是跟回溯一样 试着cur 迭代

          画个图
     */
    public TreeNode deserialize(String data) {
        String[] s = data.split(",");
        TreeNode headRoot = new TreeNode(Integer.parseInt(s[0]));

        Queue<TreeNode> q = new LinkedList<>(); // 核心数据结构
        q.offer(headRoot); // 将起点加入队列
        int curInd = 0; // 妙：i+1 i+2 拿节点
        int step = 0; // 记录扩散的步数

        while (!q.isEmpty()) {
            int oldSize = q.size();
            /* 将当前队列中的所有节点向四周扩散 */
            for (int i = 0; i < oldSize; i++) {
                TreeNode cur = q.poll();
                int curIndTmp = curInd; // * 上面++ 了 下面 +2=+3了， 所以要用tmo
                if (cur == null) { // 下方 队列 null 要加，因为是序列化占位用的 -> 之后 上方 判断是null判断即可
                    continue;
                }
                // 1 指向 i+1 i+2 并 放入 队列  并 ind++
                if (curIndTmp + 1 < s.length) {
                    if (s[curIndTmp + 1].equals("null")) {
                        cur.left = null;
                        q.add(null);
                    } else {
                        cur.left = new TreeNode(Integer.parseInt(s[curIndTmp + 1]));
                        q.add(cur.left);
                    }
                    curInd++;
                }
                if (curIndTmp + 2 < s.length) {
                    if (s[curIndTmp + 2].equals("null")) {
                        cur.right = null;
                        q.add(null);
                    } else {
                        cur.right = new TreeNode(Integer.parseInt(s[curIndTmp + 2]));
                        q.add(cur.right);
                    }
                    curInd++;
                }
            }
            step++;
        }
        return headRoot;
    }

    /*

    */
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root); // 广搜 初始 必须+root
        sb.append(root.val + ","); // 少

        while (!q.isEmpty()) {
            TreeNode cur = q.poll();

            // left
            if (cur.left != null) {
                q.add(cur.left);
                sb.append(cur.left.val + ","); // 核
            } else if (cur.left == null) {
                sb.append("null,"); // 核
            }
            // right
            if (cur.right != null) {
                q.add(cur.right);
                sb.append(cur.right.val + ",");
            } else if (cur.right == null) {
                sb.append("null,");
            }
        }
        return sb.toString();
    }
    @Test
    public void test2(){
        TreeNode root = MHUtils.strToTree("1,2,null,3,null,4,5");
        System.out.println(serialize(root));
    }
    @Test
    public void test() {

        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        t1.left = t2;
        t1.right = t3;
        t3.left = t4;
        t3.right = t5;
        /**
         *       1
         *     2   3
         *    n n 4 5
         */

        System.out.println("序列化成->" + serialize(t1)); // 和 jdk implement Serialize 接口 一个意思

        TreeNode root = deserialize("1,2,3,null,null,4,5");
        System.out.println("->" + serialize(root)); // 和 jdk implement Serialize 接口 一个意思
    }

}
